1. Field of the Invention
The present invention relates generally to operational methods used by processors and computing devices. More particularly, the invention relates to a method and apparatus for using a data-type tag concatenated to each data word stored in memory to preserve the integrity of a data architecture.
2. Description of the Related Art
The utility of computer processors is primarily evaluated according to three criteria: speed of operation, compatibility with other systems, and reliability. A processor""s reliability depends on the data security it provides for programming and system usage. As the size of applications run on such processors has increased over the past years, so has the importance of providing such security. A large program typically consists of a large number of modules or subprograms (hereinafter referred to collectively as xe2x80x9cmodulesxe2x80x9d), each of which may have been designed and/or written by a different individual. When such modules interact, security features are necessary to isolate the effects of an error to the module in which it occurredxe2x80x94it should be impossible for an error that originates in a first module to corrupt data used by a second module and thereby interfere with the operation of the second module.
The scope of such security issues is broad, being relevant not only for protecting against innocent errors inadvertently introduced by programmers, but also for safeguarding against deliberately perpetuated malicious actions, such as may be introduced by various computer viruses. Moreover, this concept of providing data security in concert with modularity, while outlined above for an individual program, may readily be extended to encompass preserving safe interaction among multiple programs on a larger scale. A conspicuous example of such a large-scale program interaction is the internet, which can usefully be regarded as a single extended application composed of a large number of interacting programs. With the continued growth of use of the internet, the importance of maintaining data security by isolating the effects of errors to individual modular programs continues to increase.
A useful conceptual framework in which to understand approaches to data security involves xe2x80x9cuser context.xe2x80x9d This refers to all space available to the user, including registers, memory locations, files, etc., which a human user might recognize as variables, arrays, a functions, objects, modules, etc. In a more general sense, user context refers to the space available to any active agent, including a task, program, procedure, etc., in addition to a human user. In this more general sense, the user context for a function would include its local and global variables, functions, and parameters, and as well as those spaces that are pointed to by pointers within those variables and parameters. Within this framework, the requirements for data security discussed above are equivalent to requiring that user context not be expanded.
Methods for limiting user context, i.e. preventing the programs and data of one module from unauthorized access by another module, operate in part by identifying the data type of individual data words. Certain functions (such as moving pointers and descriptors) are prohibited from operating on data words that are not identified with the appropriate data type. Such data-type checking can be performed at different times, depending on the structure of the computer language used. For example, in the case of high-level languages, it is possible to check these data types and grant corresponding data-access rights to the proper modules at the time of compilation. This requires that certain static restrictions be introduced into the language, which make it nonuniversal and adversely affect its efficiency for many applications. In particular, to permit the compiler to check that pointers and descriptors are handled correctly, it is necessary to have statically known variable types that remain constant during the variable""s entire life. While this has the modest advantage that data-type checking is completed with compilation of a program, these static variables can only be moved or used for object access, and cannot be used for such operations as arithmetic or logic operations. Despite these deficiencies, several high-level languages, such as Java, adopt this tactic.
A more efficient approach involves checking variable data types dynamically at run time; this can either be done exclusively by software or may be complemented with hardware support to increase the level of efficiency even further. Both of these dynamic approaches are actively used in different languages. A number of languages, such as LISP and Smalltalk, use exclusively software-based run-time checking, which is somewhat simpler to implement but lacks the additional efficiencies possible from including hardware support.
The inclusion of hardware support lends itself to different ways of making use of that support. Common to these different ways is the notion of xe2x80x9ccapabilities.xe2x80x9d A capability is a descriptor that defines the access rights for some operational space. Such a descriptor may, for example, take the form of an array descriptor or a procedure label. With hardware support, user context can be defined by the list of capabilities that the user possesses. In order to limit user context, a capability should be protected from unauthorized modification. To implement data security features, there should therefore be both means for distinguishing capabilities from other data and there should be a mechanism for preventing ordinary data from being used as capabilities.
The most popular approach for implementing data security features with these constraints is use of a xe2x80x9ccapability list,xe2x80x9d which is a tabulation.of data types and corresponding data words stored in separate memory segments. In this approach, all pointers and descriptors are kept in special typed segments and have special operations to work with these segments. Capabilities are kept distinct from other data by imposing requirements on operators that act on data: an operation that acts on a capability (e.g. LOAD or STORE) can only get its operands from the separate memory segments where the capability list is stored; other operations (e.g. ADD or MULTIPLY) can never operate on those separate memory segments. While several processors have been built using this approach, they still suffer from significant inefficiencies, both in speed of operation and in the flexibility afforded to programmers. These inefficiencies are a direct consequence of the restriction inherent in this approach that separate memory segments be used to store the capabilities.
An alternative approach involves the use of data tags, which permit greater flexibility without significant adverse effect on efficiency. In this approach, operational spaces are not separated. Instead, data tags record the data types of data words in extra bits concatenated to each data word. As such, the inefficiency produced from storing capabilities in separate memory segments is avoided. Capabilities are separated from other data by the positioning of the tag with respect to the data words. Also, operations are defined such that only a particular set of data types are permissible for each operand. For example, the LOAD operation could be defined to load both the capability and data in the form of a tagged data word by having two operands, the first restricted to being a capability and the second restricted to being other data. An operation such as ADD would, however, require that both of its operands be numbers.
In modern processors, there is a need to handle both numeric data and non-numeric data, which can be distinguished by using separate tags. However, there has so far been no processor that has used a fully consistent set of capability-based features to provide overall tagged data integrity and protection in an architecture with several non-numeric data formats.
The present invention is directed to a method and computer apparatus for providing a secure data architecture for computer memory of a processor. The apparatus comprises a memory unit and a processing unit. Data are stored in the memory unit and manipulated by the processing unit, which is programmed to implement the data architecture. In one embodiment, a plurality of tagged single data words is formed by concatenating a tag to each of the single data words. Each of the tags takes a value that corresponds to the data type of the single data word to which it is concatenated. A data multiword is creating by concatenating a plurality of tagged single data words having the same data type. The data multiword is stored within a location in the computer memory, the location selected to ensure alignment of the data multiword in accordance with its length. An effective tag value is constructed for the data multiword by concatenating each of the tags of the tagged single data words comprised by the data multiword. An operation is prevented from being performed on the data multiword if the effective tag value is not one of a predetermined list of valid effective tag values for the operation.
In another embodiment, a plurality of tagged non-numeric single data words are formed by concatenating a tag to each of the single data words. The tag has a value that corresponds to the data type of the single data word to which it is concatenated. A plurality of non-numeric data multiwords are created, each formed by concatenating a plurality of tagged single data words having the same non-numeric data type. At least two of the data multiwords so created comprise a different number of bits. An effective tag value is constructed for each data multiword by concatenating each of the tags from the data multiword together. An operation is prevented from being performed on that data multiword if the effective tag value is not one of a predetermined list of valid effective tag value for the operation.
In still another embodiment, the invention is directed to a method and computer apparatus for providing program debugging instructions. A plurality of tagged single data words are formed by concatenating a tag to each single data word. The tag takes a value that corresponds to the data type of the single data word to which it is concatenated. A multiword is created by concatenating a plurality of tagged single data words having the same data type. The data multiword is stored within a location in a computer memory, the location selected to ensure alignment of the data multiword in accordance with its length. An effective tag value is constructed for the data multiword by concatenating each of the tags from the data multiword together. An operation is prevented from being performed on the first data multiword if the effective tag value is not one of a predetermined list of valid effective tag values for the operation. A user is notified in response to an attempt to perform the operation on the data multiword.
The tagged-word data architecture of the present invention presents numerous advantages, some of which are herein enumerated. The technique is conceptually fundamental and simple, resulting in an approach to handling a plurality of data types that is both sound and reliable. This is achieved without placing restrictions on programming freedom, except for those limitations specifically introduced for security purposes to preserve the integrity of the tagged data.
The architecture also provides a very good debugging facility because intensive run-time type checking is automatically switched on everywhere without the need to use additional resources. Many typical errors that are made by programmers are detected automatically, such as a failure to initialize data or a violation of array bounds. The normal operation of the system of the invention essentially includes a good debugger that runs automatically in the background during program execution without the need for additional speed or memory space losses.
Furthermore, the system is not oriented to any specific high-level language. Implementation of compilers for any high-level language, including Java, SmallTalk, C, and C++, is equally straightforward. All programs with this implementation, including the operating system, have good modularity and security so there is no need for a special design of a kernel for the operating system; the same programming technology is used for the kernel as for the shell and other applications, making the operating system smaller, more elegant, more efficient, and more reliable.
There is very little cost for achieving these advantages, other than the need for approximately 6% more memory space to store the tag bits. There is no loss of execution performance and the invention achieves a necessary balance between the competing requirements of system efficiency and data integrity.